"""
10.正则表达式匹配
https://leetcode-cn.com/problems/regular-expression-matching

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例1:
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例2:
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

提示:
0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符
"""
class Solution:
  """
  注: 为方便表述，以下将 p 中的 ?* 看成一个字符

  设:
    函数 f(m, n) = isMatch(s[:m], p[:n])
  则:
    isMatch(s, n) == f(len(s)+1, len(p)+1)

    f(m, n) = {
      f(m-1, n-1) and isMatch(s[m-1], p[n-1])  #(当 p[n-1] != '?*' 时),
      f(m, n-1) or (f(m-1, n) and isMatch(s[m-1], p[n-1]))  #(否则)
    }
  """
  def isMatch(self, s: str, p: str) -> bool:
    m = len(s) + 1
    n = len(p) + 1
    # 创建dp表，缓存 isMatch(s[:m], p[:n]) 的值
    dp = [[False] * n for _ in range(m)]
    # isMatch('', '') 一定是 True
    dp[0][0] = True
    # 动态规划
    for i in range(1, n-1, 2):
      if p[i] == '*':
        dp[0][i] = True
        dp[0][i+1] = True
      else:
        break
    for i in range(1, m):
      for j in range(1, n):
        if p[j-1] == '*':
          dp[i][j] = dp[i][j-1]
        elif j < n-1 and p[j] == '*':
          if p[j-1] == '.' or p[j-1] == s[i-1]:
            dp[i][j] = dp[i][j-1] or dp[i-1][j]
          else:
            dp[i][j] = dp[i][j-1]
        else:
          dp[i][j] = dp[i-1][j-1] and (p[j-1] == '.' or p[j-1] == s[i-1])
    return dp[m-1][n-1]

